package com.sheng.leetcode.year2022.month06.day27;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/06/27
 *
 * 522. 最长特殊序列 II
 *
 * 给定字符串列表 strs ，返回其中 最长的特殊序列 。如果最长特殊序列不存在，返回 -1 。
 * 特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。
 *  s 的 子序列可以通过删去字符串 s 中的某些字符实现。
 * 例如，"abc" 是 "aebdc" 的子序列，因为您可以删除"aebdc"中的下划线字符来得到 "abc" 。"aebdc"的子序列还包括"aebdc"、 "aeb" 和 "" (空字符串)。
 *
 * 示例 1：
 * 输入: strs = ["aba","cdc","eae"]
 * 输出: 3
 *
 * 示例 2:
 * 输入: strs = ["aaa","aaa","aa"]
 * 输出: -1
 *
 * 提示:
 *
 * 2 <= strs.length <= 50
 * 1 <= strs[i].length <= 10
 * strs[i] 只包含小写英文字母
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-uncommon-subsequence-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0522 {

    @Test
    public void test01(){
//        String[] strs = {"aba","cdc","eae"};
        String[] strs = {"aaa","aaa","aa"};
        System.out.println(new Solution().findLUSlength(strs));
    }

}
class Solution {
    public int findLUSlength(String[] strs) {
        int result = -1;
        for (int i = 0, j; i < strs.length; i++) {
            for (j = 0; j < strs.length; j++) {
                if (i == j) {
                    continue;
                }
                //意味着i位置的字符串是j位置字符串的子串
                if (test(strs[i], strs[j])) {
                    break;
                }
            }
            //走到这一步说明i位置的字符串是特殊字符串，获取最长的特殊字符串的长度
            if (j == strs.length) {
                result = Math.max(result, strs[i].length());
            }
        }
        return result;
    }

    public boolean test(String str1, String str2) {
        int i = 0;
        for (int j = 0; j < str2.length() && i < str1.length(); j++) {
            if (str1.charAt(i) == str2.charAt(j)) {
                i++;
            }
        }
        return i == str1.length();
    }
}
